from typing import List


from time import time 
  
  
def timer_func(func):
#This function shows the execution time of
#the function object passed 
    def wrap_func(*args, **kwargs): 
        t1 = time() 
        result = func(*args, **kwargs) 
        t2 = time() 
        print(f'Function {func.__name__!r} executed in {(t2-t1):.4f}s') 
        return result 
    return wrap_func 


class Solution:
    @timer_func
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        collect = []
        nums = sorted(nums)
        size = len(nums)

        cnt_2 = 0
        for i in range(size):
            if i > 0 and nums[i] == nums[i-1]: continue
            target = -nums[i]

            k = size - 1
            for j in range(i+1, size):
                if j > i+1 and nums[j] == nums[j-1]: continue
                while k > j and nums[k] + nums[j] > target:
                    k -= 1
                if k == j: break
                if nums[k] + nums[j] == target:
                    collect.append([nums[i], nums[j], nums[k]])

        print('cnt_2', cnt_2)
        return collect
    @timer_func
    def threeSum2(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        cnt = 0
        cnt_2 = 0
        #枚举 a
        for first in range(n):
            #需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            #c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]

            #枚举 b
            for second in range(first + 1, n):
                cnt_2 += 1
                #需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                #需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    cnt += 1
                    third -= 1
                    print(f'{first}, {second}, {third}, {0-nums[first]-nums[second]}, {nums[second]}')
                else:
                    cnt += 1
                    #如果指针重合，随着 b 后续的增加
                    #就不会有满足 a + b + c = 0 并且 b < c 的 c 了，可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        print('cnt_2', cnt_2)
        return ans



if __name__ == "__main__":
    print("三数之和")
    notice = '''
\t需要注意，使用双指针+2重循环，虽然看起来和三重循环很相似，也有3个循环，
但是完全不同，双指针的第二个和第三个循环，公用1个third索引，所以第二个循环和第3个
其实是双向解决，两个加起来的循环次数才是n'''
    print(notice)
    case = [82597,-9243,62390,83030,-97960,-26521,]
    case = case[:20]
    ret = Solution().threeSum(case)
#exit()
#print(ret)
    ret = Solution().threeSum2(case)
#print(ret)